package com.cbd.basic.algorithm.sort;

import com.alibaba.fastjson.JSON;
import lombok.extern.slf4j.Slf4j;

/**
 * 插入排序
 * 核心思想：从第二个元素开始，将当前元素与前边已排序的元素进行比较，找到合适的插入位置
 * 时间复杂度：O(n²)
 */
@Slf4j
public class InsertionSort {
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};

        log.info("before sorted array = {}", JSON.toJSONString(array));
        for (int i = 1; i < array.length; i++) {
            int temp = array[i]; // 当前元素
            int j = i - 1; // 当前元素前一个位置
            // 将比目标元素大的向后移动
            while (j >= 0 && array[j] > temp) {
                array[j + 1] = array[j];
                j --;
            }
            // 设置目标
            array[j + 1] = temp;
            log.info("sorted array = {}", JSON.toJSONString(array));
        }
        log.info("after sorted array = {}", JSON.toJSONString(array));
    }

}
